/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class ConstructBinaryTreefromPreorderandPostorderTraversal {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public TreeNode constructFromPrePost(int[] pre, int[] post) {
		int n = pre.length;
		return constructFromPrePost(pre, 0, n - 1, post, 0, n - 1);
	}

	private TreeNode constructFromPrePost(int[] pre, int i1, int i2, int[] post, int j1, int j2) {
		if (i1 > i2) {
			return null;
		}
		if (i1 == i2) {
			return new TreeNode(pre[i1]);
		}
		// 找到pre的i1,post的j2作为根
		TreeNode root = new TreeNode(pre[i1]);
		// post的j2-1作为右子树的根，在pre中找到它，并得到左右子树的大小
		int rightVal = post[j2 - 1];
		int i = i1 + 1;
		for (; i <= i2; i++) {
			if (pre[i] == rightVal) {
				break;
			}
		}
		// 左子树大小为i-i1
		int leftSize = i - i1 - 1;
		root.left = constructFromPrePost(pre, i1 + 1, i - 1, post, j1, j1 + leftSize - 1);
		root.right = constructFromPrePost(pre, i, i2, post, j1 + leftSize, j2 - 1);
		return root;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
